The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventor(s), to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
A basic problem in communications and data storage involves determining whether information received at a receiver accurately reflects information transmitted from a transmitter. Conventionally, additional verification bits (e.g., parity bits, cyclic redundancy check bits) have been added to message bits to facilitate improving confidence that a received message matches a transmitted message. The communication/data storage system, therefore typically includes an Error-Correcting Code (ECC). For example, in the encoding process, the codeword of an ECC code is constructed by adding redundancy/check bits to the data field. Low density parity check (LDPC) codes define one type of ECC.
LDPC codes are linear block codes associated with a sparse parity check matrix that can be represented as a bipartite graph. The sparsity refers to a condition where a parity check matrix for an LDPC code may be constrained to have less than a certain number of ones per column and to have less than a certain number of ones per row.
An LDPC decoder receives a vector (received vector), attempts to decode the most likely codeword corresponding to the received vector, and reports on whether the decoder vector is a valid codeword. An LDPC codeword may include message bits and redundancy bits. The redundancy bits may be, for example, parity bits. An LDPC code may be a linear (N,K) block code with K information bits mapped to a codeword of block length N. An LDPC code C can be specified in terms of a low-density (e.g., sparse) N×K binary parity check matrix. While examples are provided in terms of binary codes herein, it should be understood that similar methodologies can be applied to non-binary codes, where the word “bit” is replaced by the word “non-binary symbol”. Thus “bit node processing elements” as described and claimed herein may also include processing elements that process non-binary symbols. A codeword can be decoded in an iterative fashion where beliefs are built up about certain bits of the codeword and then those beliefs are passed along to other bits of the codeword via the check equation updates of beliefs. Decoding will continue until the constraints for a codeword have been satisfied, until a maximum number of tries (e.g., iterations through an LDPC decoder) have been attempted, or until other criteria terminate decoding.
FIG. 1 illustrates one general example of a conventional min-sum LDPC decoder 10. The decoder 10 provides a convergence flag when the convergence verification unit 12 determines that the decoder 10 has converged on a valid codeword. The syndrome and hard-decision (HD) change signals can be combined to determine whether the LDPC decoder 10 has reached convergence. The HD tracking unit 22 and the HD change signal usage is optional. In some architectures, the HD tracking unit 22 and HD change signal may not be needed. The syndrome computation unit 20 and the HD tracking unit 22 may receive an updated HD from a decoder processor 30 that is responsible for processing and/or updating bit nodes and check nodes.
The decoder processor 30 includes a code sub-matrix 36 that is a sub-matrix of a larger low-density (e.g., sparse) binary parity check matrix (not shown) that corresponds to the parity check code. The overall LDPC code typically may have dimension N−K by N bits. This code matrix is usually processed partially using the sub-matrix. For example, the sub-matrix 36 has size x by y bits, where x<N−K and y<N. The sub-matrix 36 may be used as a basic processing unit of the code. Such basic processing units may be processed in parallel (e.g., in one clock cycle). For simplicity, only the sub-matrix 36 of the entire LDPC code parity check matrix is shown in FIGS. 2 and 3. For example, the super-parity check matrix, which will be described later, may correspond to the sub-matrix 36 of the LDPC code parity check matrix.
A bit node processing element (NPE) 32 is provided for each column of the code sub-matrix 36, thus there are y bit NPEs. A check NPE 34 is provided for each row of the code sub-matrix 36, thus there are x check NPEs. In some embodiments, x may be equal to y. In min-sum decoders, the bit NPEs compute or update bit-to-check messages (Q messages), whereas the check NPEs compute or update check-to-bit messages (R messages). In some implementations, instead of storing Q messages, an a-postieri bit (P message) may be stored. The decoder processor 30 provides updated R messages to an R memory 14 and updated Q or P messages to a Q or P memory 16. The decoder processor 30 receives values from the R memory 14 and the Q or P memory 16.
In another type of LDPC decoder, the messages may be single bit messages. These decoders are often called bit-flip decoders. In one implementation of a bit-flip decoder, the P message for a bit node j (1≦j≦N) is a single bit message. This is also the HD value for that bit node. The bit node value can be updated in an iterative fashion, where the check nodes directly connected to the bit node j are polled and, based on these check node values, it is determined whether to flip the value of the bit node j or keep the current value of the bit node j. In this implementation, the R memory stores the check node values, whereas the P memory stores the bit node values (HD values). Thus, the R memory stores the value of the XOR of all the bit node values connected to the check node stored in the R memory.